//
// Created by xili on 2024/9/24 11:41.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    vector<int> numSmallerByFrequency(vector <string> &queries, vector <string> &words) {
        int n = words.size();
        vector<int> fwords(n);
        for (int i = 0; i < n; i++) {
            fwords[i] = f(words[i]);
        }
        ranges::sort(fwords);
        vector<int> ans;
        for (auto &it: queries) {
            ans.emplace_back(fwords.end() - upper_bound(fwords.begin(), fwords.end(), f(it)));
        }
        return ans;
    }

    int f(string &s) {
        char cur = s[0];
        int cnt = 1;
        int n = s.size();
        for (int i = 1; i < n; i++) {
            if (cur > s[i]) {
                cur = s[i];
                cnt = 1;
            } else if (cur == s[i]) {
                cnt++;
            }
        }
        return cnt;
    }
};